/*
 * @author zzr
 * @date: 2025/10/13  19:24
 * @description: 环形链表2 给定一个链表的头节点，返回链表开始入环的
 * 第一个节点。如果链表没有环，则返回 null
 * 结论：当 fast 和 slow 在相遇点相遇后，将其中一个引用再拉到起始点
 * 的位置，然后 fast 和 slow 再同时一步一步的向后走，下次两个引用重合的位置，就是入口点的位置
 */
public class Demo13 {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {

        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }

        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
